package SortAll;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
//        int[] arr = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1};
//        for (int i = 1; i < arr.length; i++) {
//            int temp = arr[i];  //要插入的第i个元素
//            int low = 0;
//            int high = i - 1; //插入目标元素的前 i-1 个元素
//            int mid = -1;
//            while (low <= high) {
//                mid = low + (high - low) / 2;
//                if (arr[mid] > temp) {
//                    high = mid - 1;
//                } else { // 元素相同时，也插入在后面的位置
//                    low = mid + 1;
//                }
//            }
//            // 目标位置 之后的元素 整体移动一位
//            for(int j = i - 1; j >= low; j--) {
//                arr[j + 1] = arr[j];
//            }
//            arr[low] = temp;
//        }
//        System.out.println(Arrays.toString(arr));

        int [] s={23,12,43,6,4,1,7,5};
        test3(s,0,7);
      System.out.println(Arrays.toString(s));
//      int [] arr={123,43,467,78,989,21};
//      test3(arr,0,arr.length-1);
//        System.out.println(Arrays.toString(arr));
    }

    public static  void test3(int [] num ,int begin,int end){
        if(begin>end){
            return;
        }
        int temp=num[begin];
        int i=begin;
        int j=end;
        while (i!=j){
            while (j>i&&num[j]>=temp){
                j--;
            }
            while (j>i&&num[i]<=temp){
                i++;
            }
            if(j>i){
                int t=num[i];
                num[i]=num[j];
                num[j]=t;
            }
        }
        num[begin]=num[i];
        num[i]=temp;
        test3(num,begin,i-1);
        test3(num,i+1,end);
    }
    public  static  void test(int []num,int begin,int end){
        if(begin>end)
            return;
        int temp=num[begin];
        int i=begin;
        int j=end;
        while (i!=j){
            while (j>i&&num[j]>=temp)
                j--;
            while (temp>=num[i]&&j>i)
                i++;
            if(j>i){
                int t=num[i];
                num[i]=num[j];
                num[j]=t;
            }
        }
        num[begin]=num[i];
        num[i]=temp;
        test(num, begin, i-1);
        test(num,i+1,end);
    }

    public static void test1(int arr[],int left,int right){
       if(left>right) {
           return;
       }
       int temp=arr[left];
       int i=left;
       int j=right;
       while (j!=i){
           while (j>i&&arr[j]>=temp){
               j--;
           }
           while (j>i&&arr[i]<=temp){
               i++;
           }
           if(j>i){
               int t=arr[i];
               arr[i]=arr[j];
               arr[j]=t;
           }
       }
       arr[left]=arr[i];
       arr[i]=temp;
       test1(arr,left,i-1);
       test1(arr,i+1,right);
    }

    public static void test2(int num[],int begin,int end){
        if(begin>end){
            return;
        }
        int tem=num[begin];
        int i=begin;
        int j=end;
        while (i!=j){
            while (j>i&&num[j]>=tem){
                j--;
            }
            while (j>i&&num[i]<=tem){
                i++;
            }
            if(j>i){
                int t=num[i];
                num[i]=num[j];
                num[j]=tem;
            }
        }
        num[begin]=num[i];
        num[i]=tem;
        test2(num,begin,i-1);
        test2(num,i+1,end);
    }



}
